home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 13.05 / Challenge, Othello.sit.hqx / Challenge, Othello / Jello.c next >
Text File  |  1997-03-17  |  31KB  |  1,175 lines
  1. /*
  2.  *  Jello: An nxn Othello program in C 1/97
  3.  *  Copyright 1997 Jeff Mallett
  4.  *
  5.  *  Uses alpha-beta search with iterative deepening, transposition tables, 
  6.  *  extension for solving, futility cut-off, a simplistic selectivity, etc.
  7.  */
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <time.h>
  12.  
  13. #define MY_ASSERT(b) 
  14.  
  15.  
  16. // ***********************************************************
  17. // Engine Parameters
  18. // ***********************************************************
  19.  
  20.     // Extensions/Pruning
  21.     #define kFullDepthPlies            2 // # of full-depth plies before selectivity
  22.     #define kSolveThreshold            4 // Plies extension for solving whole board
  23.     #define kMinimumSafeDisks        3 // Minimum disks to have and still be safe
  24.     #define kFutilityScore            kCorner // Score above beta to trigger futility cut-off
  25.     #define kWipeOutExtension   2 // Extend a ply if opponent doesn't have more disks than this
  26.     
  27.     // Average move time in 60ths of a second
  28.     #define kOpeningMoveTime        50 // In the opening
  29.     #define kMoveTime                        150 // Normally
  30.     #define kSolveMoveTime            800 // When trying to solve
  31.     
  32.     // Scoring Parameters
  33.     #define kFinalDisk        50    // per disk on board at the end
  34.     #define kTooFewDisks    -50 // per disk under threshold
  35.  
  36.  
  37. // ***********************************************************
  38. // Constants/Macros
  39. // ***********************************************************
  40.  
  41. #define kInfinity            110000000L
  42. #define kBestPossible    100000000L
  43.  
  44. // Directions (if se increases both x and y):
  45. //     7  6  5  4  3  2  1  0
  46. //    NE SW NW SE  N  S  W  E  (opposites are adjacent)
  47. enum { DIR_E = 0, DIR_W, DIR_S, DIR_N, DIR_SE, DIR_NW, DIR_SW, DIR_NE };
  48. enum { E  = 0x0001,
  49.        W  = 0x0002,
  50.        S  = 0x0004,
  51.        N  = 0x0008,
  52.        SE = 0x0010,
  53.        NW = 0x0020,
  54.        SW = 0x0040,
  55.        NE = 0x0080,
  56.        
  57.        E_BORDER  = 0x0100,
  58.        W_BORDER  = 0x0200,
  59.        S_BORDER  = 0x0400,
  60.        N_BORDER  = 0x0800,
  61.        SE_BORDER = 0x1000,
  62.        NW_BORDER = 0x2000,
  63.        SW_BORDER = 0x4000,
  64.        NE_BORDER = 0x8000
  65. };
  66.  
  67. // Array of squares on the board (up to 66 x 66 squares)
  68. // Each square has:
  69. //    1st 8 bits -- In this direction there's a BLACK disk that can be flipped by WHITE
  70. #define ADJACENCY                    0x000000FF // Adjacent to disk in 8 directions
  71. #define BORDER_ADJACENCY    0x0000FF00 // Adjacent to border in 8 directions
  72. #define WHITE                            0x00010000 // Is White disk here?
  73. #define BLACK                            0x00020000 // Is Black disk here?
  74. #define COLOR_BITS                0x00030000 // Mask: Is disk here?
  75. #define BORDER_BIT                0x00040000 // Is this border square?
  76. #define COLOR_BORDER_BITS    0x00070000 // Mask: Is border or disk here?
  77. #define BAD_BIT                        0x00080000 // X or C square
  78. #define EMPTYADJ_BITS            0xFFF00000 /* Top 12 bits (0-4095) */
  79.  
  80. #define BORDER_ADJACENCY_SHIFT    8
  81. #define COLOR_SHIFT                            16
  82. #define EMPTYADJ_SHIFT                    20
  83.  
  84. #define IS_NOT_EMPTY(z)            ((z) & COLOR_BORDER_BITS)
  85. #define IS_EMPTY(z)                    !IS_NOT_EMPTY(z)
  86. #define HAS_DISK(z)                    ((z) & COLOR_BITS)
  87. #define HAS_NO_DISK(z)            !HAS_DISK(z)
  88. #define IS_BORDER(z)                ((z) & BORDER_BIT)
  89. #define IS_ON_BOARD(z)            !IS_BORDER(z)
  90. #define IS_BAD(z)                        ((z) & BAD_BIT)
  91. #define IS_EDGE(z)                    ((z) & BORDER_ADJACENCY)
  92. #define IS_CORNER(z)                (gCountZeros[((z) & BORDER_ADJACENCY) >> BORDER_ADJACENCY_SHIFT] == 3)
  93.  
  94. #define OPPONENT(side)            ((side) ^ COLOR_BITS)
  95.  
  96. #define XY2INDEX(x, y)            ((y) * gRealBoardSize + (x))
  97.  
  98. #define COUNT_EMPTIES(z) \
  99.     gCountZeros[ ((z) | ((z) >> BORDER_ADJACENCY_SHIFT)) & ADJACENCY ]
  100.  
  101. #define DIR_BIT(dir)                (1L << (dir))
  102. #define OPP_DIR_BIT(dir)        gOppDirBit[dir]
  103.  
  104. #define EMPTYADJ_BIT(index)                ((index) << EMPTYADJ_SHIFT)
  105. #define GET_EMPTYADJ_INDEX(pSq)        (*(pSq) >> EMPTYADJ_SHIFT)
  106. #define SET_EMPTYADJ_INDEX(pSq, index) \
  107.     *(pSq) = (*(pSq) & ~EMPTYADJ_BITS) | EMPTYADJ_BIT(index)
  108.  
  109. // Add to end of list
  110. #define ADD_TO_EMPTYADJ(pSq) \
  111.     SET_EMPTYADJ_INDEX(pSq, gSizeEmptyAdj); \
  112.     gEmptyAdj[gSizeEmptyAdj++] = pSq
  113.  
  114. // Swap entry in list with end entry and shrink list
  115. #define REMOVE_FROM_EMPTYADJ(pSq) { \
  116.     long i = GET_EMPTYADJ_INDEX(pSq); \
  117.     unsigned long *p = gEmptyAdj[--gSizeEmptyAdj]; \
  118.     gEmptyAdj[i] = p; \
  119.     SET_EMPTYADJ_INDEX(p, i); \
  120. }
  121.     
  122. #define PUSH(x)                *(gChangesEnd++) = (x)
  123. #define START_SAVE        PUSH(0L)
  124. #define PUSH_SQ(pSq)     { PUSH(*(pSq)); PUSH((unsigned long)(pSq)); }
  125. #define POP                        *(--gChangesEnd)
  126. #define TOP                        *gChangesEnd
  127.  
  128. typedef unsigned long * PSQUARE;
  129. typedef long SCORE;
  130.  
  131. #define USE_HASH
  132. #ifdef USE_HASH
  133.     #define kHashTableMask        0x7FFF // 32K entry table
  134.     #define kHashTableSize        (kHashTableMask + 1)
  135.     #define kSwitchSideHash        0x87654321
  136.     enum { INVALID = 0, VALID = 1, LOWER_BOUND = 2, UPPER_BOUND = 3 };
  137.  
  138.     typedef struct SHash {
  139.         unsigned long HashValue;
  140.         SCORE Score;
  141.         PSQUARE BestMove;
  142.         short Depth;
  143.         short Type;
  144.     } SHash;
  145.     
  146.     static SHash *gHashTable;
  147.     static long gWhiteHashOffset, gBlackHashOffset, gFlipHashOffset;
  148.     static unsigned long gHashValue;
  149. #endif
  150.  
  151.  
  152. // ***********************************************************
  153. // Prototypes
  154. // ***********************************************************
  155.  
  156. Boolean /*legalMove*/ Othello (
  157.   long boardSize,    /* number of rows/columns in the game board */
  158.   long oppRow,       /* row where opponent last moved, 0 .. boardSize-1 */
  159.   long oppCol,       /* column where opponent last moved, 0 .. boardSize-1 */
  160.   long *moveRow,     /* return your move - row, 0 .. boardSize-1 */
  161.   long *moveCol,     /* return your move - column, 0 .. boardSize-1 */
  162.   void *privStorage, /* preallocated storage for your use */
  163.   long storageSize,  /* size of privStorage in bytes */
  164.   Boolean newGame,   /* TRUE if this is your first move in a new game */
  165.   Boolean playBlack  /* TRUE if you play first (black pieces) */
  166. );
  167.  
  168. static SCORE Search(SCORE alpha, SCORE beta, unsigned long side, long depth, Boolean passEndsGame);
  169. static long Generate(unsigned long side);
  170. static SCORE MakeMove(PSQUARE to, unsigned long side);
  171. static void UnmakeMove();
  172. static void Initialize(long boardSize, void *privStorage);
  173. static SCORE Evaluate(unsigned long side);
  174. static long SortValue(PSQUARE p, unsigned long side);
  175. static void BubbleSort(long n, unsigned long side);
  176.  
  177.  
  178. // ***********************************************************
  179. // Static Variables
  180. // ***********************************************************
  181.  
  182. // Direction indices
  183. static unsigned long gOppDirBit[8] = { W, E, N, S, NW, SE, NE, SW };
  184.  
  185. // Offsets on board plus zero sentinel
  186. // Fill in gOffsets[2..7] when we know board size
  187. static long gOffsets[9] = {1L,-1L,99L,99L,99L,99L,99L,99L,0L};
  188.  
  189. // gSquares -- Array of squares: Stores board
  190. static unsigned long *gSquares; 
  191. static unsigned long *gOnBoardStart; // Pointer into gSquares
  192. static unsigned long *gOnBoardEnd; // Pointer into gSquares
  193. static long gNumOnSquares; // # of squares, not including borders
  194. static long gRealBoardSize; // Length of a side (includes borders)
  195.  
  196. // gEmptyAdj -- Array of pointers to squares: Stores all empty squares adjacent to disk(s)
  197. static PSQUARE *gEmptyAdj; 
  198. static long gSizeEmptyAdj;
  199.  
  200. // gChanges -- Array of unsigned longs containing data to undo moves
  201. //     list of:
  202. //          <pointer to square> <old square value>
  203. //     terminated by a OL
  204. //   The first position will be the drop square and the others will be flips
  205. static unsigned long *gChanges;
  206. static unsigned long *gChangesEnd; // Pointer into gChanges
  207.  
  208. // gCountZeros -- Precalculated 256-element constant array
  209. //     returns count of zero bits in the byte
  210. static unsigned long *gCountZeros;
  211.  
  212. // gTree -- Array of pointers to squares: Holds search tree
  213. static PSQUARE *gTree;
  214. static PSQUARE *gTreeEnd; // Pointer into gTree
  215.  
  216. // gMobility -- Array of counts of moves available at each ply
  217. static long *gMobility;
  218.  
  219. // Pointers to various special squares
  220. static PSQUARE gNWCorner, gNWX, gNWC1, gNWC2;
  221. static PSQUARE gNECorner, gNEX, gNEC1, gNEC2;
  222. static PSQUARE gSWCorner, gSWX, gSWC1, gSWC2;
  223. static PSQUARE gSECorner, gSEX, gSEC1, gSEC2;
  224.  
  225. // The gCounts array holds current counts of disks
  226. // Access is by gCounts[side >> COLOR_SHIFT] 
  227. //   gCounts[WHITE_INDEX] white's disks
  228. //   gCounts[BLACK_INDEX] black's disks
  229. #define WHITE_INDEX        (WHITE >> COLOR_SHIFT)
  230. #define BLACK_INDEX        (BLACK >> COLOR_SHIFT)
  231. static unsigned long gCounts[3];
  232.  
  233. static SCORE gIncScore; // Score relative to side to move
  234. static SCORE gEndgameDiskBonus; // Bonus per disk in endgame
  235. static SCORE kX, kC, kEdge, kCorner; // Penalties/Bonuses
  236.  
  237. static long gAbortSearchTime; // Time at which the search will be aborted
  238. static Boolean gAborted; // Has the search been aborted?
  239.  
  240. static long gStartDepth; // Search was started at this depth
  241. static long gPly; // Number of moves deep
  242.  
  243.  
  244.  
  245. // ***********************************************************
  246. // Othello
  247. // ***********************************************************
  248. Boolean /*legalMove*/ Othello (
  249.   long boardSize,    /* number of rows/columns in the game board */
  250.   long oppRow,       /* row where opponent last moved, 0 .. boardSize-1 */
  251.   long oppCol,       /* column where opponent last moved, 0 .. boardSize-1 */
  252.   long *moveRow,     /* return your move - row, 0 .. boardSize-1 */
  253.   long *moveCol,     /* return your move - column, 0 .. boardSize-1 */
  254.   void *privStorage, /* preallocated storage for your use */
  255.   long storageSize,  /* size of privStorage in bytes */
  256.   Boolean newGame,   /* TRUE if this is your first move in a new game */
  257.   Boolean playBlack  /* TRUE if you play first (black pieces) */
  258. )
  259. {
  260.     PSQUARE *to, p;
  261.     unsigned long side = playBlack ? BLACK : WHITE;
  262.     unsigned long nextSide;
  263.     SCORE t, bestScore, saveIncScore;
  264.     long j, generated, index, x, y;
  265.     long stillOpen, bestFoundAt, *pOffsets;
  266.     long startTime, targetTime, targetDuration;
  267.     Boolean nearEdge;
  268. #ifdef USE_HASH
  269.     unsigned long saveHashValue;
  270. #endif
  271.  
  272.     if (newGame) {
  273.         Initialize(boardSize, privStorage);
  274.     }
  275.     gChangesEnd = gChanges;
  276.     
  277. #ifdef USE_HASH
  278.     // Fix up gHashTable
  279.     {
  280.         SHash *pHashTable = gHashTable;
  281.         int i;
  282.         
  283.         i = kHashTableSize - 1;
  284.         do {
  285.             (pHashTable++)->Depth -= 2;
  286.         } while (i--);
  287.     }
  288. #endif
  289.  
  290.     if (oppRow != -1) {
  291.         index = XY2INDEX(oppCol+1, oppRow+1);
  292.         gIncScore -= MakeMove(&gSquares[index], playBlack ? WHITE : BLACK);
  293.         gChangesEnd = gChanges;
  294.     }
  295.     
  296.     gTreeEnd = gTree;
  297.     generated = Generate(side);
  298.     
  299.     if (!generated) { // No moves
  300.         *moveRow = *moveCol = -1;
  301.         return TRUE;
  302.     }
  303.     
  304.     if (generated > 1 && !(newGame && oppRow == -1)) {
  305.         BubbleSort(generated, side);
  306.         
  307.         gMobility[0] = gMobility[1] = generated;
  308.         gPly = 1;
  309.         
  310.         nextSide = OPPONENT(side);
  311.         stillOpen = gNumOnSquares - gCounts[WHITE_INDEX] - gCounts[BLACK_INDEX];
  312.  
  313.         // Calculate gEndgameDiskBonus
  314.         gEndgameDiskBonus = 0;
  315.         x = gNumOnSquares / 3;
  316.         j = x - stillOpen;
  317.         if (j > 0) {
  318.             gEndgameDiskBonus = (j * kFinalDisk) / (x * 5);
  319.             if (!gEndgameDiskBonus)
  320.                 gEndgameDiskBonus = 1;
  321.         }
  322.  
  323.         // Do we have any pieces near an edge?
  324.         nearEdge = false;
  325.         for (p = gOnBoardStart; !nearEdge && p <= gOnBoardEnd; ++p) {
  326.             if (HAS_DISK(*p)) {
  327.                 if (IS_EDGE(*p)) {
  328.                     nearEdge = true;
  329.                 } else {
  330.                     pOffsets = gOffsets;
  331.                     do {
  332.                         if (IS_EDGE(*(p + *pOffsets)))
  333.                             nearEdge = true;
  334.                     } while (!nearEdge && *(++pOffsets));
  335.                 }
  336.             }
  337.         }
  338.         
  339.         // Set times
  340.         if (!nearEdge)
  341.             targetDuration = kOpeningMoveTime;
  342.         else if (stillOpen > 20)
  343.             targetDuration = kMoveTime;
  344.         else // try to solve!
  345.             targetDuration = kSolveMoveTime;
  346.         startTime = LMGetTicks();
  347.         targetTime = startTime + targetDuration;
  348.         gAbortSearchTime = startTime + targetDuration * 6;
  349.         gAborted = false;
  350.  
  351.         saveIncScore = gIncScore;
  352. #ifdef USE_HASH
  353.         saveHashValue = gHashValue;
  354. #endif
  355.  
  356.         for (gStartDepth=1; gStartDepth < stillOpen && !gAborted; ++gStartDepth) {
  357.             to = gTree;
  358.             bestScore = -kInfinity;
  359.             for (j=0; j<generated; ++j) {
  360.                 gIncScore = - (gIncScore + MakeMove(*to, side));
  361.                     ++gPly;
  362.                     t = -Search(-kInfinity, kInfinity, nextSide, gStartDepth - 1, false);
  363.                     --gPly;
  364.                 UnmakeMove();
  365.                 gIncScore = saveIncScore;
  366. #ifdef USE_HASH
  367.                 gHashValue = saveHashValue;
  368. #endif
  369.                 if (gAborted)
  370.                     break;
  371.                     
  372.                 if (t > bestScore) {                    
  373.                     PSQUARE bestMove, *p;
  374.                     // Move *to to front of the tree
  375.                     bestMove = *to;
  376.                     MY_ASSERT(bestMove >= gOnBoardStart && bestMove <= gOnBoardEnd);
  377.                     for (p = to; p != gTree; --p)
  378.                         *p = *(p-1);
  379.                     *gTree = bestMove;
  380.                     
  381.                     bestScore = t;
  382.                     bestFoundAt = gStartDepth;
  383.                 }
  384.                 if (LMGetTicks() >= targetTime) {
  385.                     if (bestScore > -kInfinity && gStartDepth + kSolveThreshold + 1 != stillOpen)
  386.                         break; // time to stop
  387.                     if (LMGetTicks() - startTime >= 3 * targetDuration)
  388.                         break; // time to stop
  389.                 }
  390.                 ++to;
  391.             }
  392.             
  393.             if (gStartDepth >= 4 && LMGetTicks() - startTime > 1 + targetDuration/2)
  394.                 break; // probably not enough time to finish another iteration
  395.             if (gStartDepth - bestFoundAt == 3 && IS_CORNER(*gTree[0]))
  396.                 break; // easy corner move
  397.         }
  398.     }
  399.     
  400.     gIncScore += MakeMove(*gTree, side);
  401.     index = (long)(*gTree - gSquares);
  402.     y = index / gRealBoardSize;
  403.     x = index - y * gRealBoardSize;
  404.     *moveCol = x - 1;
  405.     *moveRow = y - 1;
  406.     
  407.     return TRUE;
  408. }
  409.  
  410. // ***********************************************************
  411. // SortValue
  412. // ***********************************************************
  413. // Returns value that orders squares for root search
  414. long SortValue(PSQUARE p, unsigned long side)
  415. {
  416.     long stillOpen, value;
  417.     PSQUARE q;
  418.     unsigned long occupant, enemy;
  419.     long *pOffsets;
  420.     
  421.     if (IS_EDGE(*p)) {
  422.         if (IS_CORNER(*p))
  423.             return 200; // Corner
  424.         if (IS_BAD(*p))
  425.             return -100; // C
  426.         return 100; // Edge
  427.     }
  428.     if (IS_BAD(*p))
  429.         return -200; // X
  430.     
  431.     // Check p's adjacency bits
  432.     stillOpen = gNumOnSquares - gCounts[WHITE_INDEX] - gCounts[BLACK_INDEX];
  433.     enemy = OPPONENT(side);
  434.     value = 0;
  435.     pOffsets = gOffsets;
  436.     do {
  437.         q = p + *pOffsets;
  438.         occupant = *q & COLOR_BITS;
  439.         if (stillOpen > 10) {
  440.             if (occupant == side)
  441.                 ++value; // good to take away empty-adjacent
  442.             else if (occupant == enemy)
  443.                 --value; // bad to flip
  444.         } else if (occupant == OPPONENT(side))
  445.             ++value; // endgame: good to flip
  446.     } while (*(++pOffsets));
  447.     
  448.     return value;
  449. }
  450.  
  451. // ***********************************************************
  452. // BubbleSort
  453. // ***********************************************************
  454. // Sorts generated root moves in decreasing value order
  455. // Hey, bubble sort is really okay in this case
  456. void BubbleSort(long n, unsigned long side)
  457. {
  458.     long i, j, swaps;
  459.     PSQUARE temp;
  460.     
  461.     for (j=n-2; j>=0; --j) {
  462.         swaps = 0;
  463.         i = 0;
  464.         do {
  465.             if (SortValue(gTree[i+1], side) > SortValue(gTree[i], side)) {
  466.                 ++swaps; // Swap i and i+1
  467.                 temp = gTree[i];
  468.                 gTree[i] = gTree[i+1];
  469.                 gTree[i+1] = temp;
  470.             }
  471.         } while (i++ != j);
  472.         if (!swaps)
  473.             break; // Already sorted: Finish early
  474.     }
  475. }
  476.  
  477. // ***********************************************************
  478. // Evaluate
  479. // ***********************************************************
  480. // Evaluate position and return score relative to side
  481. // side is also the side to move
  482. SCORE Evaluate(unsigned long side)
  483. {
  484.     SCORE score = 0;
  485.     
  486.     // Maximize disks, but only in endgame
  487.     if (gEndgameDiskBonus) {
  488.         score = (gCounts[WHITE_INDEX] - gCounts[BLACK_INDEX]) * gEndgameDiskBonus;
  489.         if (side == BLACK)
  490.             score = -score;
  491.     }
  492.  
  493.     // NW Corner Area
  494.     if (HAS_DISK(*gNWCorner)) {
  495.         score += (*gNWCorner & side) ? kCorner : -kCorner;
  496.     } else if (*gNWCorner & ADJACENCY) {
  497.         if (HAS_DISK(*gNWX)) {
  498.             score += (*gNWX & side) ? kX : -kX;
  499.         }
  500.         if (HAS_DISK(*gNWC1)) {
  501.             score += (*gNWC1 & side) ? kC : -kC;
  502.         }
  503.         if (HAS_DISK(*gNWC2)) {
  504.             score += (*gNWC2 & side) ? kC : -kC;
  505.         }
  506.     }
  507.  
  508.     // NE Corner Area
  509.     if (HAS_DISK(*gNECorner)) {
  510.         score += (*gNECorner & side) ? kCorner : -kCorner;
  511.     } else if (*gNECorner & ADJACENCY) {
  512.         if (HAS_DISK(*gNEX)) {
  513.             score += (*gNEX & side) ? kX : -kX;
  514.         }
  515.         if (HAS_DISK(*gNEC1)) {
  516.             score += (*gNEC1 & side) ? kC : -kC;
  517.         }
  518.         if (HAS_DISK(*gNEC2)) {
  519.             score += (*gNEC2 & side) ? kC : -kC;
  520.         }
  521.     }
  522.  
  523.     // SW Corner Area
  524.     if (HAS_DISK(*gSWCorner)) {
  525.         score += (*gSWCorner & side) ? kCorner : -kCorner;
  526.     } else if (*gSWCorner & ADJACENCY) {
  527.         if (HAS_DISK(*gSWX)) {
  528.             score += (*gSWX & side) ? kX : -kX;
  529.         }
  530.         if (HAS_DISK(*gSWC1)) {
  531.             score += (*gSWC1 & side) ? kC : -kC;
  532.         }
  533.         if (HAS_DISK(*gSWC2)) {
  534.             score += (*gSWC2 & side) ? kC : -kC;
  535.         }
  536.     }
  537.  
  538.     // SE Corner Area
  539.     if (HAS_DISK(*gSECorner)) {
  540.         score += (*gSECorner & side) ? kCorner : -kCorner;
  541.     } else if (*gSECorner & ADJACENCY) {
  542.         if (HAS_DISK(*gSEX)) {
  543.             score += (*gSEX & side) ? kX : -kX;
  544.         }
  545.         if (HAS_DISK(*gSEC1)) {
  546.             score += (*gSEC1 & side) ? kC : -kC;
  547.         }
  548.         if (HAS_DISK(*gSEC2)) {
  549.             score += (*gSEC2 & side) ? kC : -kC;
  550.         }
  551.     }
  552.     
  553.     // Too few disks?
  554.     if (gCounts[WHITE_INDEX] < kMinimumSafeDisks) {
  555.         SCORE x = (kMinimumSafeDisks - gCounts[WHITE_INDEX]) * kTooFewDisks;
  556.         score += (side == WHITE) ? x : -x * 2;
  557.     }
  558.     if (gCounts[BLACK_INDEX] < kMinimumSafeDisks) {
  559.         SCORE x = (kMinimumSafeDisks - gCounts[BLACK_INDEX]) * kTooFewDisks;
  560.         score += (side == BLACK) ? x : -x * 2;
  561.     }
  562.     
  563.     // Mobility
  564.     score += gMobility[gPly-2] - gMobility[gPly-1];
  565.     
  566.     // Could also have a value for the right to move
  567.     
  568.     return gIncScore + score;
  569. }
  570.  
  571. // ***********************************************************
  572. // Search
  573. // ***********************************************************
  574. SCORE Search(SCORE alpha, SCORE beta, unsigned long side, long depth, Boolean passEndsGame)
  575. {
  576.     register PSQUARE *to;
  577.     unsigned long nextSide;
  578.     long generated;
  579.     SCORE t, bestScore, saveIncScore;
  580.     PSQUARE *firstMove;
  581.     long stillOpen;
  582.     SCORE oldAlpha = alpha;
  583. #ifdef USE_HASH
  584.     unsigned long saveHashValue;
  585.     PSQUARE bestMove, tableReply;
  586.     SHash *pHashTable;
  587. #endif    
  588.     
  589.     stillOpen = gNumOnSquares - gCounts[WHITE_INDEX] - gCounts[BLACK_INDEX];
  590.     if (!stillOpen) {
  591.         // Board full
  592.         bestScore = (gCounts[WHITE_INDEX] - gCounts[BLACK_INDEX]) * kFinalDisk;
  593.         if (side == BLACK)
  594.             bestScore = -bestScore;
  595.         return bestScore;
  596.     }
  597.     
  598.     if (!gCounts[WHITE_INDEX]) {
  599.         // White is wiped out!
  600.         bestScore = kBestPossible;
  601.         if (side == WHITE)
  602.             bestScore = -kBestPossible;
  603.         return bestScore;
  604.     }
  605.     
  606.     if (!gCounts[BLACK_INDEX]) {
  607.         // Black is wiped out!
  608.         bestScore = kBestPossible;
  609.         if (side == BLACK)
  610.             bestScore = -kBestPossible;
  611.         return bestScore;
  612.     }
  613.     
  614.     if (depth <= 0) {
  615.         if (stillOpen > kSolveThreshold &&
  616.                 gCounts[OPPONENT(side) >> COLOR_SHIFT] > kWipeOutExtension) {
  617.             bestScore = Evaluate(side);
  618. #ifdef USE_HASH
  619.             bestMove = NULL;
  620. #endif    
  621.             goto HashSave; // Terminal node
  622.         }
  623.     } else if (depth == 1 && stillOpen > kSolveThreshold) {
  624.         t = Evaluate(side);
  625.         if (t > beta + kFutilityScore)
  626.             return t; // Futility cut-off
  627.     }
  628.  
  629. #ifdef USE_HASH
  630.     tableReply = NULL;
  631.     pHashTable = &gHashTable[gHashValue & kHashTableMask];
  632.     if (pHashTable->HashValue == gHashValue) {
  633.         tableReply = pHashTable->BestMove;
  634.         if (pHashTable->Depth >= depth) {
  635.             if (pHashTable->Type == VALID) {
  636.                 if (pHashTable->Score > beta)
  637.                    alpha = beta;
  638.                 else if (pHashTable->Score > alpha)
  639.                     alpha = pHashTable->Score;
  640.             } else if (pHashTable->Type == LOWER_BOUND) {
  641.                 if (pHashTable->Score > beta)
  642.                     return beta + 1;
  643.             } else if (pHashTable->Type == UPPER_BOUND) {
  644.                 if (pHashTable->Score < alpha)
  645.                     return alpha - 1;
  646.             }
  647.             if (alpha > beta)
  648.                 return beta;
  649.         }
  650.     }
  651. #endif
  652.     
  653.     // Abort?
  654.     if (LMGetTicks() >= gAbortSearchTime) {
  655.         gAborted = true;
  656.         return 0;
  657.     }
  658.  
  659. #ifdef USE_HASH
  660.     bestMove = NULL;
  661. #endif    
  662.     nextSide = OPPONENT(side);
  663.  
  664.     firstMove = gTreeEnd;
  665.     generated = Generate(side);
  666.     gMobility[gPly] = generated;
  667.     
  668.     if (!generated) { // no moves available
  669.         if (passEndsGame) {
  670.             bestScore = (gCounts[WHITE_INDEX] - gCounts[BLACK_INDEX]) * kFinalDisk;
  671.             if (side == BLACK)
  672.                 bestScore = -bestScore;
  673.             return bestScore;
  674.         }
  675. #ifdef USE_HASH
  676.         gHashValue ^= kSwitchSideHash;
  677. #endif
  678.         gIncScore = -gIncScore;
  679.         ++gPly;
  680.             bestScore = -Search(-beta, -alpha, nextSide, depth, true);
  681.         --gPly;
  682.         gIncScore = -gIncScore;
  683.         ++depth;
  684.         goto Searched;
  685.      }
  686.  
  687.     to = firstMove;
  688.     bestScore = -kInfinity;
  689.  
  690. #ifdef USE_HASH    
  691.     if (tableReply && *to != tableReply) {
  692.         // Find tableReply in move list and move to front
  693.         PSQUARE *p;
  694.         for (p = to + 1; *p; ++p)
  695.             if (*p == tableReply) {
  696.                 // Swap *p and *to
  697.                 *p = *to;
  698.                 *to = tableReply;
  699.                 break;
  700.             }
  701.     }
  702. #endif
  703.  
  704.     saveIncScore = gIncScore;
  705. #ifdef USE_HASH
  706.     gHashValue ^= kSwitchSideHash;
  707.     saveHashValue = gHashValue;
  708. #endif
  709.  
  710.     do {
  711.         if (!IS_BAD(**to) || // selectivity
  712. #ifdef USE_HASH
  713.                     !bestMove ||
  714. #endif
  715.                     gStartDepth - depth <= kFullDepthPlies ||
  716.                     stillOpen <= kSolveThreshold) {
  717.             gIncScore = - (gIncScore + MakeMove(*to, side));
  718.             ++gPly;
  719.                 t = -Search(-beta, -alpha, nextSide, depth-1, false);
  720.             --gPly;
  721.             UnmakeMove();
  722.             gIncScore = saveIncScore;
  723. #ifdef USE_HASH
  724.             gHashValue = saveHashValue;
  725. #endif
  726.  
  727.             if (gAborted) {
  728. #ifdef USE_HASH
  729.                 bestMove = NULL;
  730. #endif
  731.                 break;
  732.             }
  733.             
  734.             if (t > bestScore) {
  735. #ifdef USE_HASH
  736.                 bestMove = *to;
  737. #endif
  738.                 if (t > alpha) {
  739.                     if (t >= beta) {
  740.                         bestScore = t;
  741.                         break;
  742.                     }
  743.                     alpha = t;
  744.                 }
  745.                 bestScore = t;
  746.             }
  747.         }
  748.         ++to;        
  749.     } while (*to);
  750.  
  751. Searched: ;
  752. #ifdef USE_HASH
  753.     gHashValue ^= kSwitchSideHash;
  754. #endif
  755.     gTreeEnd = firstMove;
  756.  
  757. #ifdef USE_HASH
  758.     if (bestMove) {
  759. #endif
  760. HashSave: ;
  761. #ifdef USE_HASH
  762.         pHashTable = &gHashTable[gHashValue & kHashTableMask];
  763.         if (pHashTable->Depth <= depth) {
  764.             pHashTable->HashValue = gHashValue;
  765.             pHashTable->Depth = depth;
  766.             pHashTable->Score = bestScore;
  767.             pHashTable->BestMove = bestMove;
  768.             MY_ASSERT(!bestMove || IS_EMPTY(*bestMove));
  769.             
  770.             pHashTable->Type = VALID;
  771.             if (bestScore <= oldAlpha) {
  772.                 pHashTable->Type = UPPER_BOUND;
  773.             } else if (bestScore >= beta) {
  774.                 pHashTable->Type = LOWER_BOUND;
  775.             }
  776.         }
  777.     }
  778. #endif
  779.  
  780.     return bestScore;
  781. }
  782.  
  783. // ***********************************************************
  784. // Generate
  785. // ***********************************************************
  786. #define ADD_MOVE(pSq)        *(gTreeEnd++) = pSq
  787. long Generate(unsigned long side)
  788. {
  789.     PSQUARE *e, p, q, *afterCorners, *movesStart, lastBad;
  790.     unsigned long enemy;
  791.     long i, *pOffsets;
  792.     
  793.     enemy = OPPONENT(side);
  794.     afterCorners = movesStart = gTreeEnd;
  795.     lastBad = NULL;
  796.         
  797.     e = gEmptyAdj;
  798.     i = gSizeEmptyAdj;
  799.     while (i--) {
  800.         p = *e;
  801.         MY_ASSERT(IS_EMPTY(*p) && (*p & ADJACENCY));
  802.         pOffsets = gOffsets;
  803.         do {
  804.             q = p + *pOffsets;
  805.             if (*q & enemy) {
  806.                 do { // Skip through line of enemy disks
  807.                     q += *pOffsets;
  808.                 } while (*q & enemy);
  809.                 if (*q & side) { // Add square p to move list!
  810.                     // Bad?  Try to put it on the end
  811.                     if (IS_BAD(*p)) {
  812.                         if (!lastBad) {
  813.                             lastBad = p;
  814.                             break;
  815.                         }
  816.                         ADD_MOVE(p);
  817.                         break;
  818.                     }
  819.                     if (!IS_CORNER(*p)) {
  820.                         // Add to end after corners
  821.                         ADD_MOVE(p);
  822.                         break;
  823.                     }
  824.                     // Corner: keep all corners on front
  825.                     if (afterCorners == gTreeEnd) { // All are corners!
  826.                         ADD_MOVE(p);
  827.                     } else {
  828.                         unsigned long *temp = *afterCorners;
  829.                         *afterCorners = p;
  830.                         ADD_MOVE(temp);
  831.                     }
  832.                     ++afterCorners;
  833.                     break;
  834.                 }
  835.             }
  836.         } while (*(++pOffsets));
  837.         ++e;
  838.     }
  839.     if (lastBad) {
  840.         ADD_MOVE(lastBad);
  841.     }
  842.     ADD_MOVE(NULL); // sentinel
  843.     return (long)(gTreeEnd - movesStart) - 1;
  844. }
  845.  
  846. // ***********************************************************
  847. // MakeMove
  848. // ***********************************************************
  849. // Makes the move for "side" on the "to" square
  850. // Saves the move to gChanges for later undo'ing
  851. // Returns the change in score relative to the moving side
  852. SCORE MakeMove(PSQUARE to, unsigned long side)
  853. {
  854.     unsigned long z;
  855.     PSQUARE q, p;
  856.     long dir, offset;
  857.     long flips = 0;
  858.     SCORE score = 0;
  859.     unsigned long enemy = OPPONENT(side);
  860.  
  861.     MY_ASSERT(IS_EMPTY(*to) && (*to & ADJACENCY));
  862.     
  863. #ifdef USE_HASH
  864.     // Update hash for new disk
  865.     if (side == BLACK)
  866.         gHashValue ^= *(to + gBlackHashOffset);
  867.     else
  868.         gHashValue ^= *(to + gWhiteHashOffset);
  869. #endif
  870.  
  871.     START_SAVE;
  872.     
  873.     // Do flipping, Update adjacency
  874.     dir = 7;
  875.     do {
  876.         offset = gOffsets[dir];
  877.         q = to + offset;
  878.         if (IS_ON_BOARD(*q)) {            
  879.             if (IS_EMPTY(*q)) {
  880.                 if ( !(*q & ADJACENCY) ) { // First adjacent
  881.                     ADD_TO_EMPTYADJ(q);
  882.                 }
  883.                 score--; // New disk touches empty, which is bad
  884.             } else if (*q & enemy) {
  885.                 // Skip through line of enemy disks
  886.                 p = q + offset;
  887.                 while (*p & enemy)
  888.                     p += offset;
  889.                     
  890.                 if (*p & side) { // Flip 'em
  891.                     p = q;
  892.                     do {
  893.                         // Flip disk at p
  894.                         ++flips;
  895.                         if (IS_EDGE(*p))
  896.                             score += kEdge;
  897.                         PUSH_SQ(p);
  898.                         score -= (COUNT_EMPTIES(*p) << 1); // x2  Empties counted for us now
  899.                         *p ^= COLOR_BITS; // Flip
  900. #ifdef USE_HASH
  901.                         gHashValue ^= *(p + gFlipHashOffset); // Update hash for flipped disk
  902. #endif
  903.                         p += offset;
  904.                     } while (*p & enemy);
  905.                     score++; // Fills in area around disk at q which is now ours
  906.                 } else {
  907.                     score--; // Fills in area around disk at enemy disk at q
  908.                 }
  909.             } else { // *q & side
  910.                 score++; // Fills in area around our disk at q
  911.             }
  912.             z = OPP_DIR_BIT(dir);
  913.             MY_ASSERT((*q & z) == 0L);
  914.             *q |= z;
  915.         }
  916.     } while (dir--);
  917.  
  918.     PUSH_SQ(to);
  919.     REMOVE_FROM_EMPTYADJ(to);
  920.     *to |= side;
  921.  
  922.     PUSH(gCounts[WHITE_INDEX]);
  923.     PUSH(gCounts[BLACK_INDEX]);
  924.     gCounts[side >> COLOR_SHIFT] += flips + 1;
  925.     gCounts[enemy >> COLOR_SHIFT] -= flips;
  926.     
  927.     if (IS_EDGE(*to))
  928.         score += kEdge;
  929.     
  930.     return score;
  931. }
  932.  
  933. // ***********************************************************
  934. // UnmakeMove
  935. // ***********************************************************
  936. void UnmakeMove()
  937. {    
  938.     PSQUARE to, flipped, q;
  939.     unsigned long z;
  940.     long dir;
  941.     
  942.     // Restore disk counts
  943.     gCounts[BLACK_INDEX] = POP;
  944.     gCounts[WHITE_INDEX] = POP;
  945.  
  946.     // Replace to-disk
  947.     to = (PSQUARE)POP;
  948.     *to = POP;
  949.     ADD_TO_EMPTYADJ(to);
  950.  
  951.     // Undo disk changes
  952.     while (POP) {
  953.         flipped = (PSQUARE)TOP;
  954.         *flipped = POP;
  955.     }
  956.  
  957.     // Update adjacency
  958.     dir = 7;
  959.     do {
  960.         q = to + gOffsets[dir];
  961.         z = OPP_DIR_BIT(dir);
  962.         *q &= ~z; // Remove adjacency (if not already removed from disk changes)
  963.         if ( IS_EMPTY(*q) && !(*q & ADJACENCY) ) { // First adjacent
  964.             REMOVE_FROM_EMPTYADJ(q);
  965.         }
  966.     } while (dir--);
  967. }
  968.  
  969. // ***********************************************************
  970. // Initialize
  971. // ***********************************************************
  972. void Initialize(long boardSize, void *privStorage)
  973. {
  974.     unsigned long *p, *q;
  975.     long i, index, numRealSquares;
  976.     char *ptr;
  977.     unsigned long z;
  978. #ifdef USE_HASH
  979.     unsigned long r1, r2;
  980. #endif
  981.  
  982.     kX      = -2 - boardSize * 5;
  983.     kC      = -2 - boardSize * 4;
  984.     kEdge   = 3 + boardSize / 8;
  985.     kCorner = 2 + boardSize * 13;
  986.     
  987.     gRealBoardSize = boardSize + 2;
  988.     gNumOnSquares = boardSize * boardSize;
  989.     numRealSquares = gRealBoardSize * gRealBoardSize;
  990.     
  991.     ptr = privStorage;
  992.  
  993.     gSquares = (unsigned long *)ptr;
  994.     gOnBoardStart = gSquares + gRealBoardSize + 1;
  995.     gOnBoardEnd   = gSquares + (gRealBoardSize * (gRealBoardSize - 1) - 2);
  996.     ptr += numRealSquares * 4;
  997.     // worst case 66*66*4 = 17,424 bytes (~17K)
  998.     
  999. #ifdef USE_HASH
  1000.     gWhiteHashOffset = numRealSquares;
  1001.     gBlackHashOffset = numRealSquares * 2;
  1002.     gFlipHashOffset  = numRealSquares * 3;
  1003.     ptr += (numRealSquares * 3) * 4;
  1004.     // worst case 66*66*3*4 = 52,272 bytes (~51K)
  1005.     
  1006.     gHashTable = (SHash *)ptr;
  1007.     ptr += kHashTableSize * sizeof(SHash);
  1008.     // 32768*16 = 524,288 bytes (512K)
  1009. #endif
  1010.  
  1011.     gEmptyAdj = (PSQUARE *)ptr;    
  1012.     ptr += gNumOnSquares * 4;
  1013.     // worst case 64*64*4 = 16,384 bytes (16K)
  1014.     
  1015.     gChanges = (unsigned long *)ptr;
  1016.     ptr += 65536; // e.g. 64 moves (deep) * 256 longs/move * 4 bytes/long
  1017.     // 65,536 bytes (64K)
  1018.  
  1019.     gMobility = (long *)ptr;
  1020.     ptr += 1024; // e.g. 256 moves deep * 4 bytes/long
  1021.     // 1,024 bytes (1K)
  1022.     
  1023.     gCountZeros = (unsigned long *)ptr;
  1024.     ptr += 256 * 4;
  1025.     // 256*4 = 1,024 bytes (1K)
  1026.     
  1027.     gTree = (PSQUARE *)ptr;
  1028.     // Gets what's left, almost 400K!
  1029.  
  1030.  
  1031.     // ** Calculate directional offsets
  1032.     gOffsets[DIR_S]  = gRealBoardSize;
  1033.     gOffsets[DIR_N]  = - gRealBoardSize;
  1034.     gOffsets[DIR_SE] = gRealBoardSize + 1;
  1035.     gOffsets[DIR_NW] = - gRealBoardSize - 1;
  1036.     gOffsets[DIR_NE] = - gRealBoardSize + 1;
  1037.     gOffsets[DIR_SW] = gRealBoardSize - 1;
  1038.     
  1039.     // ** Borders
  1040.     //   Upper/Lower
  1041.     p = gSquares;
  1042.     q = gSquares + (gRealBoardSize * (gRealBoardSize - 1));
  1043.     i = gRealBoardSize;
  1044.     do {
  1045.         *(p++) = BORDER_BIT;
  1046.         *(q++) = BORDER_BIT;
  1047.     } while (--i);
  1048.     
  1049.     //   Sides
  1050.     p = gSquares + gRealBoardSize;
  1051.     i = gRealBoardSize - 2;
  1052.     do {
  1053.         *p = BORDER_BIT;
  1054.         p += (gRealBoardSize - 1);
  1055.         *(p++) = BORDER_BIT;
  1056.     } while (--i);    
  1057.     
  1058.     // ** Edges
  1059.     //   Upper/Lower
  1060.     p = gOnBoardStart;
  1061.     q = gOnBoardEnd;
  1062.     i = boardSize;
  1063.     do {
  1064.         *(p++) = NW_BORDER | N_BORDER | NE_BORDER;
  1065.         *(q--) = SW_BORDER | S_BORDER | SE_BORDER;
  1066.     } while (--i);
  1067.  
  1068.     //   Sides
  1069.     p = gOnBoardStart;
  1070.     q = gOnBoardEnd;
  1071.     i = boardSize;
  1072.     do {
  1073.         *p |= NW_BORDER | W_BORDER | SW_BORDER;
  1074.         *q |= NE_BORDER | E_BORDER | SE_BORDER;
  1075.         p += gRealBoardSize;
  1076.         q -= gRealBoardSize;
  1077.     } while (--i);
  1078.     
  1079.     // ** Starting configuration
  1080.     // Set up initial disks and adjacent empty squares
  1081.     // "On your first move, you should initialize the board
  1082.     // with white tiles at (row,col) = (boardSize/2-1,boardSize/2-1) and
  1083.     // (boardSize/2,boardSize/2), and black tiles at (boardSize/2-1,boardSize/2)
  1084.     // and (boardSize/2,boardSize/2-1)"
  1085.     gCounts[WHITE_INDEX] = gCounts[BLACK_INDEX] = 2;
  1086.  
  1087.     gSizeEmptyAdj = 12;
  1088.     i = boardSize >> 1; // x2
  1089.     index = XY2INDEX(i-1, i-1);
  1090.     
  1091.     p = &gSquares[index];
  1092.     *p = SE; gEmptyAdj[0] = p;
  1093.     *(++p) = EMPTYADJ_BIT(1) | S | SE; gEmptyAdj[1] = p;
  1094.     *(++p) = EMPTYADJ_BIT(2) | SW | S; gEmptyAdj[2] = p;
  1095.     *(++p) = EMPTYADJ_BIT(3) | SW; gEmptyAdj[3] = p;
  1096.     
  1097.     p += gRealBoardSize - 3;
  1098.     *p = EMPTYADJ_BIT(4) | E | SE; gEmptyAdj[4] = p;
  1099.     *(++p) = WHITE | S | SE | E;
  1100.     *(++p) = BLACK | W | SW | S;
  1101.     *(++p) = EMPTYADJ_BIT(5) | W | SW; gEmptyAdj[5] = p;
  1102.     
  1103.     p += gRealBoardSize - 3;
  1104.     *p = EMPTYADJ_BIT(6) | E | NE; gEmptyAdj[6] = p;
  1105.     *(++p) = BLACK | N | NE | E;
  1106.     *(++p) = WHITE | W | NW | N;
  1107.     *(++p) = EMPTYADJ_BIT(7) | W | NW; gEmptyAdj[7] = p;
  1108.     
  1109.     p += gRealBoardSize - 3;
  1110.     *p = EMPTYADJ_BIT(8) | NE; gEmptyAdj[8] = p;
  1111.     *(++p) = EMPTYADJ_BIT(9) | N | NE; gEmptyAdj[9] = p;
  1112.     *(++p) = EMPTYADJ_BIT(10) | NW | N; gEmptyAdj[10] = p;
  1113.     *(++p) = EMPTYADJ_BIT(11) | NW; gEmptyAdj[11] = p;
  1114.  
  1115.     gNWCorner = gOnBoardStart;
  1116.     gNWC1 = gNWCorner + 1; *gNWC1 |= BAD_BIT;
  1117.     gNWC2 = gNWCorner + gRealBoardSize; *gNWC2 |= BAD_BIT;
  1118.     gNWX = gNWC2 + 1; *gNWX |= BAD_BIT;
  1119.  
  1120.     gNECorner = gNWCorner + boardSize - 1;
  1121.     gNEC1 = gNECorner - 1; *gNEC1 |= BAD_BIT;
  1122.     gNEC2 = gNECorner + gRealBoardSize; *gNEC2 |= BAD_BIT;
  1123.     gNEX = gNEC2 - 1; *gNEX |= BAD_BIT;
  1124.     
  1125.     gSWCorner = gOnBoardEnd - boardSize + 1;
  1126.     gSWC1 = gSWCorner + 1; *gSWC1 |= BAD_BIT;
  1127.     gSWC2 = gSWCorner - gRealBoardSize; *gSWC2 |= BAD_BIT;
  1128.     gSWX = gSWC2 + 1; *gSWX |= BAD_BIT;
  1129.     
  1130.     gSECorner = gOnBoardEnd;
  1131.     gSEC1 = gSECorner - 1; *gSEC1 |= BAD_BIT;
  1132.     gSEC2 = gSECorner - gRealBoardSize; *gSEC2 |= BAD_BIT;
  1133.     gSEX = gSEC2 - 1; *gSEX |= BAD_BIT;
  1134.     
  1135.     // Precalculate gCountZeros
  1136.     // (Could have had the compiler fill these in, but I'm not
  1137.     //  THAT desperate for speed)
  1138.     for (z=0; z<256; ++z) {
  1139.         gCountZeros[z] =
  1140.             8 - (z & 1) - ((z>>1) & 1) - ((z>>2) & 1) - ((z>>3) & 1) -
  1141.             ((z>>4) & 1) - ((z>>5) & 1) - ((z>>6) & 1) - ((z>>7) & 1);
  1142.     }
  1143.  
  1144. #ifdef USE_HASH
  1145.     gHashValue = 0xFFFFFFFF;
  1146.     
  1147.     // Initialize gHashKeys
  1148.     srand(0x1234); //srand(time(NULL));    
  1149.     for (i=0; i<numRealSquares; ++i) {
  1150.         r1 = rand() + ((unsigned long)rand() << 16);
  1151.         r2 = rand() + ((unsigned long)rand() << 16);
  1152.         gSquares[gWhiteHashOffset + i] = r1;
  1153.         gSquares[gBlackHashOffset + i] = r2;
  1154.         gSquares[gFlipHashOffset  + i] = r1 ^ r2;
  1155.     }
  1156.  
  1157.     // Clear gHashTable
  1158.     {
  1159.         SHash *pHashTable = gHashTable;
  1160.         
  1161.         i = kHashTableSize - 1;
  1162.         do {
  1163.             pHashTable->HashValue = 0;
  1164.             pHashTable->Depth = -100;
  1165.             pHashTable->BestMove = NULL;
  1166.             pHashTable->Type = INVALID;
  1167.             pHashTable->Score = 0;
  1168.             ++pHashTable;
  1169.         } while (i--);
  1170.     }
  1171. #endif
  1172.     
  1173.     gIncScore = 0;
  1174. }
  1175.